#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <string>
 
struct HuffmanNode {
    char ch;
    unsigned freq;
    HuffmanNode *left, *right;
 
    HuffmanNode(char ch, unsigned freq) : ch(ch), freq(freq), left(nullptr), right(nullptr) {}
};
 
struct Compare {
    bool operator()(HuffmanNode* l, HuffmanNode* r) {
        return l->freq > r->freq; // 最小堆，根据频率排序
    }
};
HuffmanNode* buildHuffmanTree(const std::map<char, int>& frequency) {
    std::priority_queue<HuffmanNode*, std::vector<HuffmanNode*>, Compare> pq;
    for (auto pair : frequency) {
        pq.push(new HuffmanNode(pair.first, pair.second));
    }
 
    while (pq.size() != 1) {
        HuffmanNode *left = pq.top(); pq.pop();
        HuffmanNode *right = pq.top(); pq.pop();
        HuffmanNode *merged = new HuffmanNode('$', left->freq + right->freq); // 虚拟字符'$'用于内部节点
        merged->left = left;
        merged->right = right;
        pq.push(merged);
    }
    return pq.top(); // 返回树的根节点
}
void generateCodes(HuffmanNode* root, std::string str, std::map<char, std::string>& huffmanCode) {
    if (root == nullptr) return;
    if (!root->left && !root->right) { // 叶节点
        huffmanCode[root->ch] = str;
    }
    generateCodes(root->left, str + "0", huffmanCode); // 左子树编码为0
    generateCodes(root->right, str + "1", huffmanCode); // 右子树编码为1
}
int main() {
    std::string text = "this is an example for huffman encoding";
    std::map<char, int> frequency; // 计算字符频率
    for (char ch : text) {
        frequency[ch]++; // 统计字符出现次数
    }
    HuffmanNode* root = buildHuffmanTree(frequency); // 构建哈夫曼树
    std::map<char, std::string> huffmanCode; // 存储编码结果
    generateCodes(root, "", huffmanCode); // 生成编码
    for (auto pair : huffmanCode) { // 输出每个字符的编码
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    return 0;
}